package org.review.algorithm.sort;

import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int arr[] = {53, 3, 542, 748, 14, 214};
        impl(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }


    }

    public static void impl(int[] arr) {
        int max = getMax(arr);
        int[][] bucket = new int[10][arr.length];
        int[] elementCount = new int[10];
        for (int n = 1; max / n > 0; n *= 10) {

            for (int i = 0; i < arr.length; i++) {
                int digit = (arr[i] / n) % 10;
                bucket[digit][elementCount[digit]++] = arr[i];
            }
            //TODO 2024/9/10: 将bucket内的数据取出来
            int index = 0;
            for (int i = 0; i < elementCount.length; i++) {
                if (elementCount[i] != 0) {
                    for (int j = 0; j < elementCount[i]; j++) {

                        arr[index++] = bucket[i][j];
                    }
                } elementCount[i] = 0;
            }

        }

    }

    public static int getMax(int[] arr) {
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        return max;
    }


    // 基数排序主函数
    public static void radixSort(int[] arr) {

        int max = getMax(arr);
        // 从最低位到最高位进行排序
        for (int n = 1; max / n > 0; n *= 10) {
            countingSort(arr, n);
        }

    }

    // 计数排序的子过程
    private static void countingSort(int[] arr, int exp) {
        int[] output = new int[arr.length];
        int[] count = new int[10];
        int n = arr.length;
        Arrays.fill(count, 0);

        for (int i = 0; i < n; i++) {
            count[arr[i] / exp % 10]++;
        }

        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

        System.arraycopy(output, 0, arr, 0, n);
    }
}
